{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "## Открытый курс по машинному обучению. Сессия № 2\n",
    "</center>\n",
    "Автор материала: программист-исследователь Mail.ru Group, старший преподаватель Факультета Компьютерных Наук ВШЭ Юрий Кашницкий. Материал распространяется на условиях лицензии [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center>Занятие 8. Разреженные данные, онлайн-обучение</center>\n",
    "\n",
    "## <center>Часть 1. Категориальные признаки</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### <center>One-hot encoding</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Подавляющее большинство методов классификации и регрессии сформулированы в терминах евклидовых или метрических пространств, то есть подразумевают представление данных в виде вещественных векторов одинаковой размерности. В реальных данных, однако, не так редки категориальные атрибуты, принимающие дискретные значения, такие как да/нет или  январь/февраль/.../декабрь. В ходе этого занятия мы научимся работать с такими данными, в частности с помощью линейных моделей."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import sklearn.feature_extraction\n",
    "import sklearn.linear_model\n",
    "import sklearn.metrics\n",
    "import sklearn.model_selection\n",
    "import sklearn.preprocessing\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "from pprint import pformat\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.style.use(\"ggplot\")\n",
    "import warnings\n",
    "\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части занятия мы рассмотрим выборку bank:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"../../data/bank_train.csv\")\n",
    "labels = pd.read_csv(\"../../data/bank_train_target.csv\", header=None)\n",
    "\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Нетрудно заметить, что достаточно много признаков в этом наборе данных не представлены числами. В таком виде данные еще нам не подходят - мы не сможем применять подавляющее большинство доступных нам методов.\n",
    "\n",
    "Чтобы найти решение, давайте рассмотрим атрибут education:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df[\"education\"].value_counts().plot.barh();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Естественным решением такой проблемы было бы однозначное отображение каждого значения в уникальное число. К примеру, мы могли бы преобразовать university.degree в 0, а basic.9y в 1. Эту простую операцию приходится делать часто, поэтому в модуле preprocessing библиотеки sklearn именно для этой задачи реализован класс LabelEncoder:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "label_encoder = sklearn.preprocessing.LabelEncoder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метод fit этого класса находит все уникальные значения и строит таблицу для соответствия каждой категории некоторому числу, а метод transform непосредственно преобразует значения в числа. После fit у label_encoder будет доступно поле classes, содержащее все уникальные значения. Пронумеруем их, чтобы убедиться, что преобразование выполнено верно. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mapped_education = pd.Series(label_encoder.fit_transform(df[\"education\"]))\n",
    "mapped_education.value_counts().plot.barh()\n",
    "print(dict(enumerate(label_encoder.classes_)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Что произойдет, если у нас появятся данные с другими категориями?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "try:\n",
    "    label_encoder.transform(df[\"education\"].replace(\"high.school\", \"high_school\"))\n",
    "except Exception as e:\n",
    "    print(\"Error:\", e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Таким образом, при использовании этого подхода мы всегда должны быть уверены, что признак не может принимать неизвестных ранее значений. К этой проблеме мы вернемся чуть позже, а сейчас заменим весь столбец education на преобразованный:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df[\"education\"] = mapped_education\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Продолжим преобразование для всех столбцов, имеющих тип object - именно этот тип задается в pandas для таких данных."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "categorical_columns = df.columns[df.dtypes == \"object\"].union([\"education\"])\n",
    "for column in categorical_columns:\n",
    "    df[column] = label_encoder.fit_transform(df[column])\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Основная проблема такого представления заключается в том, что числовой код создал евклидово представление для данных.\n",
    "\n",
    "К примеру, нами неявным образом была введена алгебра над значениями работы - мы можем вычесть работу клиента 1 из работы клиента 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.loc[1].job - df.loc[2].job"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Конечно же, эта операция не имеет никакого смысла. Но именно на этом основаны метрики близости объектов, что делает бессмысленным применение метода ближайшего соседа на данных в таком виде. Аналогичным образом, никакого смысла не будет иметь применение линейных моделей. Убедимся в этом:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def logistic_regression_accuracy_on(dataframe, labels):\n",
    "    features = dataframe.as_matrix()\n",
    "    (\n",
    "        train_features,\n",
    "        test_features,\n",
    "        train_labels,\n",
    "        test_labels,\n",
    "    ) = sklearn.model_selection.train_test_split(features, labels)\n",
    "\n",
    "    lr = sklearn.linear_model.LogisticRegression()\n",
    "    lr.fit(train_features, train_labels)\n",
    "    return sklearn.metrics.classification_report(test_labels, lr.predict(test_features))\n",
    "\n",
    "\n",
    "print(logistic_regression_accuracy_on(df[categorical_columns], labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для того, чтобы мы смогли применять линейные модели на таких данных нам необходим другой метод, который называется one-hot encoding.\n",
    "\n",
    "Предположим, что некоторый признак может принимать 10 разных значений. В этом случае one hot encoding подразумевает создание 10 признаков, все из которых равны нулю *за исключением одного*. На позицию, соответствующую численному значению признака мы помещаем 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "one_hot_example = pd.DataFrame([{i: 0 for i in range(10)}])\n",
    "one_hot_example.loc[0, 6] = 1\n",
    "one_hot_example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Эта техника реализована в sklearn в классе OneHotEncoder. По умолчанию OneHotEncoder преобразует данные в разреженную матрицу, чтобы не расходовать память на хранение многочисленных нулей. Однако в этом примере размер данных не является для нас проблемой, поэтому мы будем использовать \"плотное\" представление."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "onehot_encoder = sklearn.preprocessing.OneHotEncoder(sparse=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Преобразуем категориальные столбцы с помощью OneHotEncoder:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "encoded_categorical_columns = pd.DataFrame(\n",
    "    onehot_encoder.fit_transform(df[categorical_columns])\n",
    ")\n",
    "encoded_categorical_columns.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы получили 53 столбца - именно столько различных уникальных значений могут принимать категориальные столбцы исходной выборки. Преобразованные с помощью one-hot encoding данные начинают обретать смысл для линейной модели:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(logistic_regression_accuracy_on(encoded_categorical_columns, labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <center>Hashing trick</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реальные данные могут оказаться гораздо более динамичными и мы не всегда можем рассчитывать, что категориальные признаки не будут принимать новых значений. Все это сильно затрудняет использование уже обученных моделей на новых данных. Кроме того, LabelEncoder подразумевает предварительный анализ всей выборки и хранение построенных отображений в памяти, что затрудняет работу в режиме больших данных.\n",
    "\n",
    "Для решения этих проблем существует более простой подход к векторизации категориальных признаков, основанный на хэшировании, известный как hashing trick. \n",
    "\n",
    "Хэш-функции могут помочь нам в задаче поиска уникальных кодов для различных значений атрибутов, к примеру:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for s in (\"university.degree\", \"high.school\", \"illiterate\"):\n",
    "    print(s, \"->\", hash(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Отрицательные и настолько большие по модулю значения нам не подойдут. Ограничим область значений хэш-функции:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hash_space = 25\n",
    "for s in (\"university.degree\", \"high.school\", \"illiterate\"):\n",
    "    print(s, \"->\", hash(s) % hash_space)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Представим, что у нас в выборке есть холостой студент, которому позвонили в понедельник, тогда его вектор признаков будет сформирован аналогично one-hot encoding, но в **едином пространстве фиксированного размера для всех признаков**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hashing_example = pd.DataFrame([{i: 0.0 for i in range(hash_space)}])\n",
    "for s in (\"job=student\", \"marital=single\", \"day_of_week=mon\"):\n",
    "    print(s, \"->\", hash(s) % hash_space)\n",
    "    hashing_example.loc[0, hash(s) % hash_space] = 1\n",
    "hashing_example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоит обратить внимание, что в этом примере хэшировались не только значения атрибутов, а **пары название атрибута + значение атрибута**. Это необходимо, чтобы разделить одинаковые значения разных атрибутов между собой, к примеру:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert hash(\"no\") == hash(\"no\")\n",
    "assert hash(\"housing=no\") != hash(\"loan=no\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Может ли произойти коллизия хэш-функции, то есть совпадение кодов для двух разных значений? Нетрудно доказать, что при достаточном размере пространства хэширования это происходит редко, но даже в тех случаях, когда это происходит, это не будет приводить к существенному ухудшению качества классификации или регрессии.\n",
    "\n",
    "В следующей части занятия мы будем применять подход на основе хэширования для работы с категориальными данными."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
